#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class distance {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        int dp[m + 1][n + 1];

        // 初始化dp table
        for (int i = 0; i <= m; i++)
            dp[i][0] = i;
        for (int i = 0; i <= n; i++)
            dp[0][i] = i;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    // 当前字符匹配，不需要操作
                    dp[i][j] = dp[i - 1][j - 1];
                else 
                    // 字符不匹配，取delete，add，replace三种操作所需步骤最小者
                    // delete: dp[i][j] = dp[i - 1][j] + 1
                    // add: dp[i][j] = dp[i][j - 1] + 1
                    // replace: dp[i][j] = dp[i - 1][j - 1] + 1
                    dp[i][j] = min( {dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1} );
            }
        }

        return dp[m][n];
    }
};

class maxArraySum {
public:
    int maxSubArray(vector<int>& nums) {
        int length = nums.size();
        int dp_before = nums[0];
        int dp_now = 0;
        int ans = nums[0];

        for (int i = 1; i < length; i++) {
            // dp[i]只与dp[i - 1]有关，所以只需记录两个数据
            dp_now = max(nums[i], dp_before + nums[i]);
            dp_before = dp_now;
            ans = max(ans, dp_now);
        }

        return ans;
    }
};

class LIS {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp[i]表示以nums[i]为结尾的递增子序列长度
        int length = nums.size();
        int dp[length];
        for (int i = 0; i < length; i++) 
            // 将dp[i]初始化为1，递增子序列至少包含本身
            dp[i] = 1;

        for (int i = 0; i < length; i++) {
            // 遍历dp table
            for (int j = 0; j < i; j++) {
                // 遇到nums[j]小于nums[i]，说明可能存在nums[i]结尾的更长的递增子序列
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        int ans = 0;
        for (int i = 0; i < length; i++) 
            // 遍历dp table，找到最长子序列
            ans = max(ans, dp[i]);
        return ans;
    }

    int logNlengthOfLIS(vector<int>& nums) {
        int length = nums.size();
        int piles = 0;
        int top[length];
        // 二分查找解法

        for (int i = 0; i < length; i++) {
            int poker = nums[i];
            int left = 0, right = piles;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (top[mid] >= poker)
                    right = mid;
                else 
                    left = mid + 1;
            }
            if (left == piles)
                piles++;
            top[left] = poker;
        }

        return piles;
    }
};